package com.woniuxy.test_map.my_hashmap;

/**
 * description: SxHashMap <br>
 * date: 2022/2/4 12:21 上午 <br>
 * author: shesaifei <br>
 * version: 1.0 <br>
 */

/**
 * 自定义HashMap
 * 增加toString方法
 * 增加get方法
 * 增加泛型
 */
public class SxHashMap04<K, V> {
    //核心数组(位桶数组 bucket array)
    Node2[] table;
    int size; //存放键值对的个数

    public SxHashMap04() {
        table = new Node2[16]; //一般定义成2的整数幂
    }

    public V get(K key) {
        int hash = myHash(key.hashCode(), table.length);
        V value = null;
        if (table[hash] != null) {
            Node2 temp = table[hash];
            while (temp != null) {
                if (temp.key.equals(key)) { //如果相等，则说明找到键值对了，返回对应的value
                    value = (V) temp.value;
                    break;
                } else {
                    temp = temp.next;
                }
            }
        }
        return value;
    }


    public void put(K key, V value) {
        //定义了新的节点对象
        Node2 newNode = new Node2();
        newNode.hash = myHash(key.hashCode(), table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Node2 temp = table[newNode.hash];

        Node2 iterLast = null;
        boolean keyRepeat = false;
        if (temp == null) {
            //此处数组元素为空，则直接将新节点放进去
            table[newNode.hash] = newNode;
            size++;
        } else {
            //此处数组不为空。则遍历对应的链表
            while (temp != null) {
                //判断key如果重复，则覆盖
                if (temp.key.equals(key)) {
                    keyRepeat = true;
                    //只覆盖value即可。其他的值(hash,key,next)保持不变
                    temp.value = value;
                    break;
                } else {
                    //key不重复，则遍历下一个
                    iterLast = temp;
                    temp = temp.next;
                }
            }
            if (!keyRepeat) {
                //没有发生key重复的情况，则添加到链表的最后
                iterLast.next = newNode;
                size++;
            }
        }
    }

    @Override
    public String toString() {
        //{10:aa,20:bb}
        StringBuilder sb = new StringBuilder("{");
        //遍历数组
        for (int i = 0; i < table.length; i++) {
            Node2 temp = table[i];

            //遍历链表
            while (temp != null) {
                sb.append(temp.key + ":" + temp.value + ",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length() - 1, '}');
        return sb.toString();
    }

    public static void main(String[] args) {
        SxHashMap04<Integer, String> m = new SxHashMap04();
        m.put(10, "aa");
        m.put(20, "bb");
        m.put(30, "cc");
        m.put(20, "ss");
        m.put(21, "gg");
        m.put(37, "hh");
        m.put(53, "xx");
        m.put(69, "zz");
        m.put(85, "pp");
        System.out.println(m);
        System.out.println(m.get(20));
        System.out.println(m.get(69));
        System.out.println(m.get(85));
//        for (int i = 0; i <100 ; i++) {
//            //相同的哈希值 5 21 37 53 69 85
//            System.out.println(i+"--"+ m.myHash(i,16));
//        }

    }

    public int myHash(int v, int length) {
        //直接位运算，效率高
        //System.out.println("hash in myHash:"+(v&(length-1)));
        //取模运算，效率低
        //System.out.println("hash in myHash:"+(v%(length-1)));
        return v & (length - 1);
    }
}
